package com.levy.sort;

public class bucket_sort {

	/**
	 * 把范围缩小到0~9来举个栗子：
	 * 
	 * 3 9 1 2 2 7 5 3 0 1 3 4 —— 原数据
	 * 
	 * [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] —— 10个桶
	 * 
	 * 0# 1# 2# 3# 4# 5# 6# 7# 8# 9# —— 桶编号
	 * 
	 * 遍历，为每个桶计数：
	 * 
	 * [1] [2] [2] [3] [1] [1] [0] [1] [0] [1]
	 * 
	 * 0# 1# 2# 3# 4# 5# 6# 7# 8# 9# —— 桶编号
	 * 
	 * 可以看到，0号桶中有1个数，1号桶中有2个数，2号桶中有2个数。。。8号桶为空，9号桶有1个数。于是将所有数据输出，0输出1次，1输出2次，2
	 * 输出2次。。。8不输出，9输出1次：
	 * 
	 * 0 1 1 2 2 3 3 3 4 5 7 9
	 */
	public static void main(String[] args) {
		int[] unsorted = { 1, 54, 6, 35, 62, 78, 12, 35, 48, 3, 5, 6, 87, 45, 16, 54 };
		int[] sorted = bucket_sort(unsorted, 100);
		for (int i = 0; i < sorted.length; i++) {
			for (int count = 0; count < sorted[i]; count++) {
				System.out.print(i + " ");
			}
		}
	}

	/**
	 * 区间不大，至少相对数组的数量不是一个级别
	 * 
	 * @param unsorted
	 * @param maxNumber
	 * @return
	 */
	static int[] bucket_sort(int[] unsorted, int maxNumber) {
		int[] sorted = new int[maxNumber];
		for (int i = 0; i < unsorted.length; i++) {
			sorted[unsorted[i]]++;
		}
		return sorted;
	}

}
